package x.y.z;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.function.Consumer;

public class LeetCode_0279 {
    public static int numSquares(int n) {
        List<Integer> list = new ArrayList<>();
        int pow = 1;
        while (pow * pow <= n) {
            list.add(pow);
            pow++;
        }
        int depth = 1;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(n);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Integer temp = queue.poll();
                for (int j = list.size() - 1; j >= 0; j--) {
                    int cur = temp - list.get(j);
                    if (cur == 0) {
                        return depth;
                    }
                    queue.offer(cur);
                }
            }
            depth++;
        }
        return depth;
    }

    public static int numSquaresDP(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                min = Math.min(min, dp[i - j * j]);
            }
            dp[i] = min+1;
        }
        return dp[n];
    }
}
